Batch 3 - Class 121 - Grid Coloring
Pre-Class Problem:
(Dudeney 259) A man was in love with a woman named HANNAH. He proposed. She wrote down her name as under.
.png)
She challenged the suitor to spell her name in as many ways as possible on the above grid, starting from any H and passing from one letter to another adjacent letter, in any direction. How many such ways exist?
- Answer: There are 17 ways to spell NAH from any N, and 17 to get to an N on a HAN. Hence for each N which leads to NAH, there are 51 ways to get the initial HAN (through 3 other N's) and 17 ways to complete NAH. Hence 17x51 ways for each N. And total 4x17x51 ways, which is 3468
Attendance: Smiti, Anshi, Arnav, Anishka, Arnav, Damini, Siddhant, Tishyaa
Class Notes:
- Tic tac toe
- Tic tac toe is a deterministic game - if two smart people are playing, the game will always end in a draw
- What if both players were playing with the same symbol X - who will win?
- Answer: If player 1 plays the center, then regardless of where player 2 plays, player 1 will win in next turn
- What if both players were playing with the same symbol X, but the person to create "three in a row" loses? Is there a winning strategy?
- Answer: If player 1 plays in the center, and then depending on player 2 turn, player 1 forces a hockey shape, player 1 should win
.png)
Grid Coloring
Can you color the vertices of a 5x5 equilateral triangle grid so that there is no equilateral triangle with vertices of same color. For example, the following fails
.png)
- Try for 6x6 equilateral triangle
- Try for 7x7 equilateral triangle
.png)
- In 2009, Bill Gasarch asked the question whether you could color 17x17 rectangle vertices so that there was no rectangle with vertices of same color. He then announced a prize of $289 (why!?) for anyone who solves it. A solution came by in 2012.
.png)
- The above solution does not have an upside rectangle of same color vertices, but there is a tilted ractangle (bottom row 6th from left, next 4th, next 7th, next 5th)
- Can you solve a simple Gasarch problem - can you color 5x5 square grid with 2 colors to satisfy above conditions? The following solution fails.
- If not, can you prove this doesn't have a solution?
- Answer: There have to be 13 vertices with same color on a 5x5 grid. Which means that at least 3 rows have to have 3 or more vertices of same color(4 or 5 vertices of same color in a row can easily be ruled out because then you can't place enough on other rows without forming a rectangle). Amongst these 3 rows, show that at least two rows have to have vertices of same color in at least 2 positions, which means those form a rectangle.
- In general, Gasarch problems fall in the NP Complete category - i.e. they are computationally very hard to solve
Homework
(Dudeney 242) A tube inspector has been appointed, and he has to inspect the 17 lines connecting 12 stations of the tube regularly. In each phase, he wants to cover as little distance as possible to inspect the entire system. Each link is 1 mile long. Provide the shortest route that enables him to do so - he is free to start and end at any station.
.png)
- Answer: 19 miles - BADGDEFIFCBEHKLIHGJK. Can also be thought of as BADEFCBEHKLIHGJK - this leaves DG and FI links which can be traversed twice whenever we are at any of these 4 stations.
References: